// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

func solveNQueens(n int) [][]string {
	var result [][]string
	var path [][]byte

	//创建 3 个布尔数组以检查给定位置是否已被占用
	col := make([]bool, n)
	diag1 := make([]bool, n<<1-1)
	diag2 := make([]bool, n<<1-1)

	//调用辅助函数生成问题的所有可能解决方案
	helper(n, 0, col, diag1, diag2, path, &result)

	return result
}

// 辅助函数是一个递归函数，它生成N皇后问题的所有可能解
func helper(n int,
	row int, col []bool, diag1 []bool, diag2 []bool,
	path [][]byte, result *[][]string) {
	//如果所有行都已填充，则将解决方案添加到结果切片
	if row >= n {
		var elem []string
		for i := 0; i < n; i++ {
			elem = append(elem, string(path[i]))
		}
		*result = append(*result, elem)
		return
	}

	//对于每一行，检查所有可能的位置以放置皇后并递归调用辅助函数
	for i := 0; i < n; i++ {
		//如果列或对角线已被占用，则跳到下一个位置
		if col[i] || diag1[row+i] || diag2[row-i+n-1] {
			continue
		}

		//在第 i 列中创建一个带有“Q”和“.”的行
		line := make([]byte, n)
		for j := 0; j < n; j++ {
			line[j] = '.'
		}
		line[i] = 'Q'

		//通过将行附加到路径来创建新路径
		newPath := append(append([][]byte{}, path...), line)

		//将位置标记为已占用
		col[i] = true
		diag1[row+i] = true
		diag2[row-i+n-1] = true

		//使用更新后的路径递归调用辅助函数
		helper(n, row+1, col, diag1, diag2, newPath, result)

		//通过将位置标记为未占用来回溯
		col[i] = false
		diag1[row+i] = false
		diag2[row-i+n-1] = false
	}
}

func main() {
	n := 4
	res := solveNQueens(n)
	fmt.Println(res)
}

//$ go run interview11-1.go
//[[.Q.. ...Q Q... ..Q.] [..Q. Q... ...Q .Q..]]
